class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        result = []
        def foo(i, exp, acc, pre):
            # print(i, exp, acc, pre)
            if i==len(num):
                if acc==target:
                    result.append(exp)
                return
            for j in range(i, len(num)):
                if j!=i and num[i]=='0': break
                next = num[i:j+1]
                cur = int(next)
                if i==0:
                    foo(j+1, exp+next, cur, cur)
                else:
                    # case +
                    foo(j+1, exp+'+'+next, acc+cur, cur)
                    # case -
                    foo(j+1, exp+'-'+next, acc-cur, -cur)
                    # case *
                    foo(j+1, exp+'*'+next, acc-pre+pre*cur, pre*cur)
        foo(0, '', 0, 0)
        return result

print(Solution().addOperators('123456789', 45))